home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / pcr / pcr4_4.lha / DIST / gc / GCmark_rescuers.c < prev    next >
C/C++ Source or Header  |  1991-05-29  |  13KB  |  448 lines
  1. /* begincopyright
  2.   Copyright (c) 1988,1990 Xerox Corporation. All rights reserved.
  3.   Use and copying of this software and preparation of derivative works based
  4.   upon this software are permitted. Any distribution of this software or
  5.   derivative works must comply with all applicable United States export
  6.   control laws. This software is made available AS IS, and Xerox Corporation
  7.   makes no warranty about the software, its performance or its conformity to
  8.   any specification. Any person obtaining a copy of this software is requested
  9.   to send their name and post office or electronic mail address to:
  10.     PCR Coordinator
  11.     Xerox PARC
  12.     3333 Coyote Hill Rd.
  13.     Palo Alto, CA 94304
  14.     
  15.   Parts of this software were derived from code bearing the copyright notice:
  16.   
  17.   Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  18.   This material may be freely distributed, provided this notice is retained.
  19.   This material is provided as is, with no warranty expressed or implied.
  20.   Use at your own risk.
  21.   
  22.   endcopyright */
  23.   
  24. /*
  25.  * Boehm, December 28, 1990
  26.  */
  27. # include "xr/GCPrivate.h"
  28.  
  29. # ifdef PRINTSTATS
  30.     static long rescuers = 0;
  31. # endif
  32.  
  33. # define MIN_MARK_SZ 10000   /* Minimum number of objects to mark at once */
  34.  
  35. /* Push all possible pointers from marked objects in the given block onto */
  36. /* the mark stack.                              */
  37. /* This is the general version.                          */
  38. static void GC_mark_block(hbp, sz)
  39. register struct hblk * hbp;
  40. register long sz;
  41. {
  42.     register word * q;
  43.     register word * p;
  44.     register word * plim;
  45.     register word potential_ptr;
  46.     register int word_no;
  47. #   ifdef PRINTSTATS
  48.       register long rescuers_reg = 0;
  49. #   endif
  50. #   ifdef SEPARATE_HEADERS
  51.     register struct hblkhdr * hhdr = HDR(hbp);
  52. #    define MARK_BIT(word_no) mark_bit_from_hdr(hhdr, word_no)
  53. #   else
  54. #    define MARK_BIT(word_no) mark_bit(hbp, word_no)
  55. #   endif
  56.  
  57.     /* Register copies of frequently referenced globals */
  58.     /* Referenced primarily from inside macros.         */
  59.       register char * GC_heapstart_reg = GC_heapstart;
  60.       register word * GC_mark_stack_top_reg = GC_mark_stack_top;
  61. #   define GC_heapstart GC_heapstart_reg
  62.  
  63.     p = (word *)(hbp->hb_body);
  64.     word_no = HDR_WORDS;
  65.     plim = (word *)((((unsigned)hbp) + HBLKSIZE)
  66.          - WORDS_TO_BYTES(sz));
  67.     do {
  68.     if (MARK_BIT(word_no)) {
  69. #           ifdef PRINTSTATS
  70.         rescuers_reg++;
  71. #           endif
  72. #           ifdef VISUALIZE
  73.         displayRoot(p, sz);
  74. #           endif
  75.         /* Copy potential pointers into mark stack */
  76.         /* and increment p by sz.                  */
  77.         /* This is time critical and therefore     */
  78.         /* done without calling GC_mark_all or the */
  79.         /* like.                                   */
  80.         q = p;
  81.         p += sz - 1;
  82.         while(q <= p) {
  83.             potential_ptr = *q;
  84.             if (quicktest(potential_ptr)) {
  85. #            define GC_mark_stack_top GC_mark_stack_top_reg
  86.             PUSH_MS(potential_ptr);
  87. #            undef GC_mark_stack_top
  88.             }
  89. #                   ifdef UNALIGNED
  90.             q = (word *)(((char *)q) + alignment);
  91. #                   else
  92.             q++;
  93. #                   endif
  94.         }
  95.         p++;
  96.     } else {
  97.         p += sz;
  98.     }
  99.     word_no += sz;
  100.     } while (p <= plim);
  101.     GC_mark_stack_top = GC_mark_stack_top_reg;
  102. #   ifdef PRINTSTATS
  103.        rescuers += rescuers_reg;
  104. #   endif
  105. #   undef GC_heapstart
  106. }
  107.  
  108. /* What follows are versions of the above specialized for different object */
  109. /* sizes.  They assume 4 byte pointer alignment.                   */
  110. /* They also assume that BODY_SZ is a multiple of 32.               */
  111.  
  112. /* A version for sz > MAXOBJSZ.  Looks at dirty bits of successive pages.  */
  113. /* Not that the first page will always be scanned since it is set if any   */
  114. /* of the subsequent pages are dirty.                       */
  115. /* Index is the index of the first page in the GC_dirty_bits array.       */
  116. static void GC_mark_large_block(hbp, sz, index)
  117. register struct hblk * hbp;
  118. register long sz;
  119. register long index;
  120. {
  121.     register word q;
  122.     register word * p;
  123.     register word * plim;
  124.     register word * limit;
  125.  
  126.     /* Register copies of frequently referenced globals */
  127.     /* Referenced primarily from inside macros.         */
  128.       register char * GC_heapstart_reg = GC_heapstart;
  129.       register word * GC_mark_stack_top_reg = GC_mark_stack_top;
  130. #   define GC_heapstart GC_heapstart_reg
  131.  
  132.     if (!mark_bit(hbp, HDR_WORDS)) return;
  133.     p = (word *)(hbp->hb_body);
  134.     limit = p + sz;
  135.     rescuers++;
  136. #   ifdef VISUALIZE
  137.     displayRoot(p, sz);
  138. #   endif
  139.     do {
  140.         plim = (word *)(((unsigned)p + HBLKSIZE) & ~HBLKMASK);
  141.     if (plim > limit) plim = limit;
  142.     if (GC_dirty_bits[index]) {
  143.         for(; p < plim; p += 2) {
  144. #        define GC_mark_stack_top GC_mark_stack_top_reg
  145.         q = p[0]; if (quicktest(q)) { PUSH_MS(q); }
  146.         q = p[1]; if (quicktest(q)) { PUSH_MS(q); }
  147. #        undef GC_mark_stack_top
  148.         }
  149.     } else {
  150.         p = plim;
  151.     }
  152.     index++;
  153.     } while (p < limit);
  154.     if (sz & 1) {
  155.         /* We unrolled inner loop once. We may have to remove the */
  156.         /* superfluous element pushed as a result.          */
  157.         if (*limit == *GC_mark_stack_top_reg
  158.             && GC_mark_stack_top_reg != GC_mark_stack_top) {
  159.             /* TOS must be copy of superfluous entry, since all stack   */
  160.             /* elements satisfy quicktest.                */
  161. #        ifdef USE_STACK
  162.         GC_mark_stack_top_reg++;
  163. #        else
  164.         GC_mark_stack_top_reg--;
  165. #        endif
  166.     }
  167.     }
  168.  
  169.     GC_mark_stack_top = GC_mark_stack_top_reg;
  170. #   undef GC_heapstart
  171. }
  172.  
  173.  
  174. /* For 2 word objects */
  175. static void GC_mark_block_2(hbp)
  176. register struct hblk * hbp;
  177. {
  178.     register word * p;
  179.     register word * plim;
  180.     register word q;
  181.     register long marks;
  182.     register long * marks_addr;
  183.     register word * GC_mark_stack_top_reg = GC_mark_stack_top;
  184.     register char * GC_heapstart_reg = GC_heapstart;
  185. #   define GC_heapstart GC_heapstart_reg
  186.     register int i;
  187. #   ifdef PRINTSTATS
  188.       register long rescuers_reg = 0;
  189. #   endif
  190.  
  191.     p = (word *)(hbp->hb_body);
  192.     plim = (word *)(((unsigned)hbp) + HBLKSIZE);
  193.     marks_addr = hb_marks(hbp);
  194.     do {
  195.         marks = *marks_addr++;
  196.     if (marks != 0) {
  197.         for (i = 0; i < WORDSZ; i += 2, p+= 2) {
  198.             if ((marks >> i) & 1) {
  199. #                   ifdef PRINTSTATS
  200.             rescuers_reg++;
  201. #                endif
  202. #                ifdef VISUALIZE
  203.             displayRoot(p, 2);
  204. #                endif
  205. #            define GC_mark_stack_top GC_mark_stack_top_reg
  206.             q = p[0]; if (quicktest(q)) { PUSH_MS(q); }
  207.             q = p[1]; if (quicktest(q)) { PUSH_MS(q); }
  208. #            undef GC_mark_stack_top
  209.         }
  210.         }
  211.     } else {
  212.         p += WORDSZ;
  213.     }
  214.     } while (p < plim);
  215.     GC_mark_stack_top = GC_mark_stack_top_reg;
  216. #   ifdef PRINTSTATS
  217.        rescuers += rescuers_reg;
  218. #   endif
  219. #   undef GC_heapstart
  220. }
  221.  
  222. /* For 4 word objects */
  223. static void GC_mark_block_4(hbp)
  224. register struct hblk * hbp;
  225. {
  226.     register word * p;
  227.     register word * plim;
  228.     register word q;
  229.     register long marks;
  230.     register long * marks_addr;
  231.     register word * GC_mark_stack_top_reg = GC_mark_stack_top;
  232.     register char * GC_heapstart_reg = GC_heapstart;
  233. #   define GC_heapstart GC_heapstart_reg
  234.     register int i;
  235. #   ifdef PRINTSTATS
  236.       register long rescuers_reg = 0;
  237. #   endif
  238.  
  239.     p = (word *)(hbp->hb_body);
  240.     plim = (word *)(((unsigned)hbp) + HBLKSIZE);
  241.     marks_addr = hb_marks(hbp);
  242.     do {
  243.         marks = *marks_addr++;
  244.     if (marks != 0) {
  245.         for (i = 0; i < WORDSZ; i += 4, p+= 4) {
  246.             if ((marks >> i) & 1) {
  247. #                   ifdef PRINTSTATS
  248.             rescuers_reg++;
  249. #                endif
  250. #                ifdef VISUALIZE
  251.             displayRoot(p, 4);
  252. #                endif
  253. #            define GC_mark_stack_top GC_mark_stack_top_reg
  254.             q = p[0]; if (quicktest(q)) { PUSH_MS(q); }
  255.             q = p[1]; if (quicktest(q)) { PUSH_MS(q); }
  256.             q = p[2]; if (quicktest(q)) { PUSH_MS(q); }
  257.             q = p[3]; if (quicktest(q)) { PUSH_MS(q); }
  258. #            undef GC_mark_stack_top
  259.         }
  260.         }
  261.     } else {
  262.         p += WORDSZ;
  263.     }
  264.     } while (p < plim);
  265.     GC_mark_stack_top = GC_mark_stack_top_reg;
  266. #   ifdef PRINTSTATS
  267.        rescuers += rescuers_reg;
  268. #   endif
  269. #   undef GC_heapstart
  270. }
  271.  
  272. /* For 8 word objects */
  273. static void GC_mark_block_8(hbp)
  274. register struct hblk * hbp;
  275. {
  276.     register word * p;
  277.     register word * plim;
  278.     register word q;
  279.     register long marks;
  280.     register long * marks_addr;
  281.     register word * GC_mark_stack_top_reg = GC_mark_stack_top;
  282.     register char * GC_heapstart_reg = GC_heapstart;
  283. #   define GC_heapstart GC_heapstart_reg
  284.     register int i;
  285. #   ifdef PRINTSTATS
  286.       register long rescuers_reg = 0;
  287. #   endif
  288.  
  289.     p = (word *)(hbp->hb_body);
  290.     plim = (word *)(((unsigned)hbp) + HBLKSIZE);
  291.     marks_addr = hb_marks(hbp);
  292.     do {
  293.         marks = *marks_addr++;
  294.     if (marks != 0) {
  295.         for (i = 0; i < WORDSZ; i += 8, p+= 8) {
  296.             if ((marks >> i) & 1) {
  297. #                   ifdef PRINTSTATS
  298.             rescuers_reg++;
  299. #                endif
  300. #                ifdef VISUALIZE
  301.             displayRoot(p, 8);
  302. #                endif
  303. #            define GC_mark_stack_top GC_mark_stack_top_reg
  304.             q = p[0]; if (quicktest(q)) { PUSH_MS(q); }
  305.             q = p[1]; if (quicktest(q)) { PUSH_MS(q); }
  306.             q = p[2]; if (quicktest(q)) { PUSH_MS(q); }
  307.             q = p[3]; if (quicktest(q)) { PUSH_MS(q); }
  308.             q = p[4]; if (quicktest(q)) { PUSH_MS(q); }
  309.             q = p[5]; if (quicktest(q)) { PUSH_MS(q); }
  310.             q = p[6]; if (quicktest(q)) { PUSH_MS(q); }
  311.             q = p[7]; if (quicktest(q)) { PUSH_MS(q); }
  312. #            undef GC_mark_stack_top
  313.         }
  314.         }
  315.     } else {
  316.         p += WORDSZ;
  317.     }
  318.     } while (p < plim);
  319.     GC_mark_stack_top = GC_mark_stack_top_reg;
  320. #   ifdef PRINTSTATS
  321.        rescuers += rescuers_reg;
  322. #   endif
  323. #   undef GC_heapstart
  324. }
  325.  
  326. /* Mark all objects reachable from previously marked objects on dirty pages */
  327. void GC_mark_rescuers(alignment)
  328. int alignment;
  329. {
  330.     register long i,j;
  331.     struct hblk * hbp;
  332.     unsigned long limit = divHBLKSZ(GC_heaplim - GC_heapstart);
  333.     long sz;
  334.     
  335.     word * plim;
  336. #   ifdef PRINTSTATS
  337.     long dirty_pages = 0;
  338. #   endif
  339.     /* Register copies of frequently referenced globals */
  340.     /* Referenced primarily from inside macros.         */
  341.       register char * GC_heapstart_reg = GC_heapstart;
  342. #   define GC_heapstart GC_heapstart_reg
  343.     /* Difference in starting point of hblkmap and GC_dirty_bits arrays */
  344.     register unsigned long offset = divHBLKSZ(GC_heapstart - VD_base);
  345.  
  346. #   ifdef PRINTSTATS
  347.     rescuers = 0;
  348. #   endif    
  349.     /* Make sure mark stack is empty */
  350.       if (GC_mark_stack_top != GC_mark_stack_bottom) {
  351.           GC_abort("GC_mark_rescuers 0");
  352.       }
  353.       
  354.     if (GC_my_objects_in_use == 0) {
  355.       /* Nothing has been marked yet.  It's safe to skip this */
  356.       return;
  357.     }
  358.     for (i = 0; i < limit; i++) {
  359.     if (hblkmap[i] == HBLK_VALID && GC_dirty_bits[i + offset]) {
  360.         hbp = (struct hblk *)(HBLKSIZE * i + GC_heapstart);
  361.         sz = hb_sz(hbp);
  362.         if (sz < 0) {
  363.         /* Atomic.  There cant be any rescuers here. */
  364.         continue;
  365.         }
  366. #           ifdef PRINTSTATS
  367.         dirty_pages++;
  368. #           endif
  369. #        if defined(UNALIGNED) || !defined(SEPARATE_HEADERS) \
  370.            || ALIGNED_DISCARD_WORDS != 0
  371.             GC_mark_block(hbp, sz);
  372. #        else
  373.         switch(sz) {
  374.             case 2:
  375.                 GC_mark_block_2(hbp);
  376.                 break;
  377.             case 4:
  378.                 GC_mark_block_4(hbp);
  379.                 break;
  380.             case 8:
  381.                 GC_mark_block_8(hbp);
  382.                 break;
  383.             default:
  384.                 if (sz > MAXOBJSZ) {
  385.                     GC_mark_large_block(hbp, sz, i + offset);
  386.                 } else {
  387.                     GC_mark_block(hbp, sz);
  388.                 }
  389.         }
  390. #        endif
  391.         /* Mark what's currently on the stack, provided there's */
  392.         /* enough there.                                        */
  393. #               ifdef USE_STACK
  394.             if (GC_mark_stack_bottom - GC_mark_stack_top
  395.                 >= MIN_MARK_SZ) {
  396.             GC_mark(alignment);
  397.             }
  398. #               else
  399.             if (GC_mark_stack_top - GC_mark_stack_bottom
  400.                 >= MIN_MARK_SZ) {
  401.             GC_mark(alignment);
  402.             }
  403. #               endif
  404.     }
  405.     }
  406.  
  407.     /* Mark anything still left to be marked at the end.  Clean up */
  408.     /* the mark stack.                                             */
  409.       if (GC_mark_stack_top != GC_mark_stack_bottom) GC_mark(alignment);
  410.  
  411. #     ifdef USE_HEAP
  412.     brk(GC_mark_stack_bottom);     /* reset break to where it was before */
  413.     GC_cur_break = (char *) GC_mark_stack_bottom;
  414. #     endif
  415.  
  416. #   ifdef VISUALIZE
  417.      /* remove root display */
  418.       for (i = 0; i < MAP_SIZE; i++) {
  419.     if (hblkmap[i] == HBLK_VALID && GC_dirty_bits[i+offset]) {
  420.         hbp = (struct hblk *)(HBLKSIZE * i + GC_heapstart);
  421.         sz = hb_sz(hbp);
  422.         if (sz < 0) {
  423.         continue;
  424.         }
  425.         if (sz > MAXOBJSZ &&
  426.         mark_bit(hbp, (hbp -> hb_body) - ((word *)(hbp))) ) {
  427.         displayMark(hbp -> hb_body, sz);
  428.         } else {
  429.         /* Small composite objects */
  430.         p = (word *)(hbp->hb_body);
  431.         word_no = p - ((word *)hbp);
  432.         plim = (word *)((((unsigned)hbp) + HBLKSIZE)
  433.              - WORDS_TO_BYTES(sz));
  434.         for (; p <= plim; p += sz, word_no += sz) {
  435.             if (mark_bit(hbp, word_no)) {
  436.             displayMark(p, sz);
  437.             }
  438.         }
  439.         }
  440.     }
  441.       }
  442. #   endif
  443. #   ifdef PRINTSTATS
  444.     GC_printf("%d dirty composite pages, %d potentially rescuing objects\n",
  445.            dirty_pages, rescuers);
  446. #   endif
  447. }
  448.